• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    ldpc design utilizing quasi-cyclic constructions and drilling for high rate, high parallelism, and low error floor. a data encoding method is disclosed. an encoder receives a set of information bits and performs a high ldpc encoding operation on the information bits to produce a codeword. the encoder then punctures all high bits of the codeword that correspond to one or more punctured base bits of a base ldpc code used for the ldpc encoding operation. the base ldpc code does not have multiple borders, and the one or more punctured base bits are those that correspond to one or more punctured base nodes, respectively, of the base ldpc code. for some embodiments, the one or more punctured base nodes correspond to one or more variable nodes of degree 2. The ldpc decoder treats punctured codeword bits as cleared during iterative decoding and operation.
    公开号:BR112015019409B1
    申请号:R112015019409-5
    申请日:2014-02-13
    公开日:2022-01-11
    发明作者:Thomas J. Richardson
    申请人:Qualcomm Incorporated；
    IPC主号:
    专利说明:

    TECHNICAL FIELD
    [0001] The present embodiments generally refer to communication and data storage systems, and specifically to communication and data storage systems that use LDPC codes. FUNDAMENTALS OF RELATED TECHNIQUE
    [0002] Many communication systems use error correction codes. Specifically, error correction codes compensate for the inherent unreliability of information transfer in these systems by introducing redundancy into the data stream. Low density parity check (LDPC) codes are a special type of error correction codes that use an iterative coding system. LDPC codes can be represented by bipartite plots (often referred to as "Tanner plots"), where a set of variable nodes corresponds to the bits of a codeword, and a set of check nodes corresponds to a set of parity checking constraints that define the code. A variable node and a check node are considered "neighbors" if they are connected by an edge on the graph. A sequence of bits having a one-to-one association with the variable node sequence is a valid codeword if and only if, for each check node, the bits associated with all neighboring variable nodes sum to zero modulo. two (ie that include the same number as the 1st).
    [0003] For example, FIG. 1A shows a bipartite graph 100 depicting an exemplary LDPC code. The split graph 100 includes a set of 5 variable nodes 110 (represented by circles) connected to 4 check nodes 120 (represented by squares). The edges of the graph 100 connect the variable nodes 110 to the check nodes 120. FIG. 1B shows a matrix representation 150 of the split graph 100. The matrix representation 150 includes a parity check matrix H and a vector x of the codeword, where x1-x5 represent bits of the codeword x. More specifically, the codeword vector x represents a valid codeword if and only if Hx = 0. FIG. 2 graphically illustrates the effect of making three copies of the graph of FIG. 1A, for example, as described in commonly owned US Patent 7,552,097. Three copies can be linked by permutation of equal edges between the copies. If the permutations are restricted to cyclic permutations, then the resulting plot corresponds to a quasi-cyclic LDPC with lift Z = 3. The original plot from which three copies were made is referred to here as the base plot.
    [0004] The received LDPC codeword may be decoded to produce a reconstructed version of the initial codeword. In the absence of errors, or in the case of correctable errors, decoding can be used to recover the original unit of data that was encoded. LDPC decoder(s) generally operate by exchanging messages within the bipartite graph 100, along the edges, and updating these messages by performing computations at the nodes based on the received messages. For example, each variable node 110 in graph 100 may initially be provided with a "soft bit" (e.g., representing the received bit of the codeword), which indicates an estimate of the value of the associated bit as determined by observations from the codeword. communications channel. Using these soft bits, LDPC decoders can update messages iteratively by reading them, or some part of them, from memory and writing an updated message, or some part of it, back to memory. Update operations are typically based on the parity check constraints of the corresponding LDPC code. In implementations for high LDPC codes, messages on equal edges are often processed in parallel.
    [0005] LDPC codes designed for high-speed applications often use quasi-cyclic constructions with large elevation factors and relatively small base graphics to support high parallelism in encoding and decoding operations. LDPC codes with higher code rates (eg, the ratio of message length K to codeword length N) tend to have relatively fewer parity checks. If the number of base parity checks is less than the degree of a variable node (e.g. the number of edges connected to a variable node), then in the base graph that variable node is linked to at least , one of the base parity checks by two or more edges (for example, the variable node can have a "double edge"). Having a variable base node and a base check node connected by two or more edges is generally undesirable for the purposes of parallel hardware implementation. For example, such double edges can result in multiple simultaneous read and write operations to the same memory locations, which in turn can create data coherence issues. The segmentation of parallel message updates can be adversely affected by the presence of double borders. SUMMARY
    [0006] This Table of Contents is provided to introduce in a simplified form a selection of concepts that are further described below in the Detailed Description. This Table of Contents is not intended to identify key features or essential features of the claimed matter, nor is it intended to limit the scope of the claimed matter.
    [0007] A device and method of operation are described that can assist in encoding and/or decoding Low Density Parity Check (LDPC) codewords. It is noted that adding a punctured variable node (also known as a state variable node) in the base graph drawing can effectively increase the number of checks on the graph by one without changing the speed (k and n) parameters of the code. For some embodiments, an encoder may receive a set of information bits and perform an LDPC encoding operation on the information bits to produce a codeword. The device may then puncture a set of high codeword bits corresponding to one or more variable-base nodes based on a high LDPC code used for the LDPC encoding operation, where the punctured bits correspond with one or more nodes. of base variables punctured, respectively, from the base LDPC graph. It is understood that variable nodes punched in the graphical description of the code can be eliminated from the description by a check node matching process operating on the high parity check matrix. Therefore, at least one of the one or more punctured base nodes is understood to eliminate the multiple edges between base graph node pairs for high LDPC code when the punctured variable node elimination results in multiple edges.
    [0008] For some embodiments, the one or more pierced nodes may include a variable node that has a degree equal to, or less than, a number of LDPC code verification nodes. For example, at least one of the punctured nodes may be a higher degree variable node of the LDPC code. In such an embodiment, high node rank is often desirable to improve code performance. For example, perforation allows for greater degree of variable node, preventing double edges in the base graph. The presence of the punctured variable node in the graph effectively increases the number of check nodes that would otherwise be present in a base graph of a code of the same size and rate. For other embodiments, at least one of the punctured nodes may be a grade two variable node used to split a check node that would otherwise be linked to a variable node of the LDPC code by two or more edges. A punctured degree two node can be eliminated from the description by adding two parity checks to which it is attached. The at least one perforated base degree two variable node can thus be used to eliminate double edges in the base LDPC plot. Likewise, a high degree punctured node can be eliminated from a parity check matrix representation by a process of elimination that sums the constraint nodes to effectively reduce the degree of the variable node to one. A grade one drilled node can be eliminated from the graph along with its neighboring check node without changing the code. Such a process of elimination is likely to introduce double or multiple edges in the representation which is undesirable for parallel execution of decoding.
    [0009] By eliminating or reducing double (or multiple) edges of the underlying LDPC graph, the present modalities can reduce the complexity of the hardware that performs LDPC decoding operations in parallel, thus increasing the processing efficiency of the LDPC decoders. LDPC that implement the elevated LDPC codes. This further simplifies read and/or write operations performed in memory, and ensures that read and write operations are not performed out of order. By allowing greater degrees of variable node, while avoiding double edges, the present modalities can also improve the error correction performance of the LDPC encoding system. BRIEF DESCRIPTION OF THE DRAWINGS
    [0010] The present arrangements are illustrated by way of example and are not intended to be limited by the figures in the accompanying drawings, where:
    [0011] FIGS. 1A-1B show graphical and matrix representations of an exemplary LDPC code;
    [0012] FIG. 2 graphically illustrates the effect of making three copies of the graph of FIG. 1A;
    [0013] FIG. 3 shows a communications system in accordance with some embodiments;
    [0014] FIG. 4 is a block diagram of a communications device according to some embodiments;
    [0015] FIG. 5 is an illustrative flowchart depicting an LDPC encoding operation in accordance with some embodiments;
    [0016] FIG. 6 is an illustrative flowchart depicting an LDPC decoding operation in accordance with some embodiments;
    [0017] FIG. 7 shows an exemplary parity check matrix associated with an LDPC code with rate r = 27/30;
    [0018] FIG. 8 shows an exemplary parity check matrix associated with an LDPC code with rate r = 13/15;
    [0019] FIG. 9 shows an exemplary parity check matrix associated with an LDPC code with rate r = 21/28; and
    [0020] FIG. 10 is a block diagram of a communications device according to some embodiments. DETAILED DESCRIPTION
    [0021] In the following description, numerous specific details are presented as examples of specific components, circuits and processes to provide a complete understanding of the present disclosure. The term "coupled" as used herein means directly connected or connected through one or more interfering components or circuits. Furthermore, in the following description and for purposes of explanation, specific nomenclature is presented to provide a thorough understanding of the present embodiments. However, it will be apparent to a person skilled in the art that these specific details may not be necessary to practice the present embodiments. In other cases, well-known circuits and devices are shown in block diagram form to avoid obscuring the present disclosure. Any of the signals provided over multiple buses described herein may be time multiplexed with other signals and provided over one or more common buses. Furthermore, the interconnection between circuit elements or software blocks can be shown as buses or as single signal lines. Each of the buses may alternatively be a single signal line, and each of the single signal lines may alternatively be the buses, and a single line or bus may represent any one or more of a myriad of physical or logical mechanisms for communication between components. The present embodiments should not be construed as being limited to the specific examples described herein, but rather as including within their scope all the embodiments defined in the appended claims.
    [0022] FIG. 3 shows a communication system 300 in accordance with some embodiments. A transmitter 310 transmits a signal over a channel 320, and a receiver 330 receives the signal from the channel 320. The transmitter 310 and receiver 330 can be, for example, computers, switches, routers, hubs, ports, and/or similar devices. In some embodiments, channel 320 is remote. In other embodiments, channel 320 is a wired link (eg, a coaxial cable or other physical connection).
    [0023] Imperfections of various components in the communications system 300 can become a source of signal impairment, and thus cause signal degradation. For example, imperfections on channel 320 can introduce channel distortion, which can include linear distortion, multipath effects, and/or Additive White Gaussian Noise (AWGN). To combat potential signal degradation, transmitter 310 and receiver 330 may include LDPC encoders and decoders. Specifically, transmitter 310 can perform LDPC encoding on the output data to produce a codeword that can be subsequently decoded by receiver 330 (e.g., through an LDPC decoding operation) to recover the original data. For some embodiments, transmitter 310 may transmit the LDPC-encoded codewords with one or more "punctured" bits, for example, based on an LDPC code with one or more punctured variable nodes.
    [0024] "Survey" allows LDPC codes to be implemented using parallel encoding and/or decoding implementations while also reducing the complexity typically associated with large LDPC codes. More specifically, lifting is a technique for generating a relatively large LDPC code from multiple copies of a smaller base code. For example, a high LDPC code can be generated by producing a number (Z) of parallel copies of the base graph and then linking the parallel copies by permutating the edge groups of each copy of the base graph. A more detailed discussion of elevated LDPC codes can be found, for example, in the book entitled, "Modern Coding Theory", published March 17, 2008, by Tom Richardson and Ruediger Urbanke, which is hereby incorporated by reference in its entirety. .
    [0025] For example, when processing a codeword with elevation Z size, an LDPC decoder can use Z processing elements to perform parity check or variable node operations on all Z edges of an elevated graph simultaneously . Specifically, each parity check operation may involve reading a corresponding soft bit value from memory, combining the soft bit value with other soft bit values associated with the check node, and writing a soft bit back. to memory, which results from the check node operation. Double edges on the base graph can trigger parallel reading of the same soft bit value, in a memory location, twice during a single parallel parity check update. Additional circuitry may thus be required to combine the soft bit values that are written back to memory in order to properly incorporate the two updates. Eliminating double edges in the base graph helps to avoid this additional complexity.
    [0026] By eliminating or reducing the double (and/or multiple) edges of the base LDPC code, punching can reduce the complexity of the hardware that performs parallel check node or variable node operations, thus increasing the efficiency of parallel processing of a corresponding LDPC decoder. This further simplifies read and/or write operations performed in memory, and ensures that read and write operations are not performed out of order.
    [0027] Punching is the act of removing bits from a codeword to produce a shorter codeword. Thus, punctured variable nodes correspond to codeword bits that are not actually transmitted. Punching a variable node in an LDPC code creates a shortened code (e.g. due to removing a bit), while also effectively removing a check node. Specifically, for an array representation of an LDPC code, including the bits to be punctured, where the variable node to be punctured has a degree of one (such a representation may be possible through given row combination in whichever code is appropriate), variable node puncturing removes the associated bit from the code and effectively removes its unique neighbor check node from the graph. As a result, the number of check nodes in the graph is reduced by one. If the transmitted base block length is n-p, where p is the number of punctured columns, and the number of base parity checks is m, then the rate is (n-m)/(n-p). The size of the binary information block is (n-m)*Z, and the transmitted block size is (n-p)*Z. Note that if we increase n and p by 1 we can increase m by 1 and leave the rate and block size unchanged.
    [0028] As an example, consider a rate code of 0.9 where the base block length is 30. Without drilling, the number of check nodes that would be used to define the base code is 3, which results in a code (27, 30) (e.g. K = 27 message bits, n = 30 codeword bits). Such code is prone to have double edges (or more) connecting at least one check node to a variable node (for example, unless all variable nodes have a maximum degree of 3). However, it may be desirable to have variable nodes of higher grade (eg grade 4), for example, to ensure a deep error floor. If a punctured variable node is introduced in the LDPC code, thus increasing the total number of variable nodes to 31, then the number of base check nodes increases to 4. It is now possible to have grade 4 base variable nodes without double borders on the base chart. We note, however, that such an LDPC code is still a code (27, 30).
    [0029] In the bipartite graph representation of an LDPC code, a grade two punctured variable node effectively combines its two neighboring check nodes into a single check node. The grade two punctured variable node effectively indicates that its two neighboring check nodes have, absent the grade two node, the same parity. Therefore, grade two punctured variable nodes can be used to "split" the check nodes, thus appearing to increase the total number of check nodes. This mechanism can therefore be used to remove multiple borders from an LDPC code. A variable node is typically linked to at least one check node by two or more edges if the degree of the variable node is greater than the total number of check nodes (N) in the base graph. Thus, multiple edges in a base graph can be avoided and/or eliminated by introducing one or more variable nodes of degree two (that is, assuming that at least one variable node in the base graph has a degree greater than N ).
    [0030] Piercing a high-grade base variable node of the LDPC code can also increase the number of check nodes. In addition, high-grade scan nodes may be desirable in high-performance LDPC design. For example, the highest degree variable node might correspond to a variable node that has a degree equal to (or less than) the total number of check nodes in the base graph. Such a high degree variable node can evidently be present in a base graph without any double edges. As described in more detail below, a punctured variable node is treated as "erased" in decoding. Thus, for codes that aim for low error rates, it may be desirable to prevent such nodes from participating in the combinatorial structures (eg, trapping sets or close codewords) that give rise to error floor events. Having a high degree generally makes it less likely that a node will contribute to an error floor event.
    [0031] Also, high-grade perforated variable nodes in the graph can improve code performance. It is known that punched nodes in a graph can improve the so-called iterative threshold of the code structure. In standard irregular LDPC models (ie, without punctured variable nodes), thresholds can be improved by increasing the average degree in the bipartite plot, and thus increasing the degree of the variable and verification nodes. With punctured variable nodes, the same effect can be achieved with lower average degree, thus reducing the complexity of the LDPC code. Also, LDPC code structures with lower average grades may perform better on smaller graphics. Thus, high-grade perforation variable nodes can either increase the number of scan nodes (thus allowing higher grades) or improve the performance of codes with limited maximum variable-node grades.
    [0032] FIG. 4 is a block diagram of a communications device 400 according to some embodiments. Communications device 400 includes an encoder 410, a decoder 420, and a transceiver 430, which transmits and/or receives LDPC-encoded codewords over a communications channel. Encoder 410 includes memory 412, and LDPC encoder 414. Memory 412 may be used to store data (ie, bits of information) to be encoded by LDPC encoder 414. LDPC encoder 414 processes the information bits stored in memory 412 by generating codewords, based on an LDPC code, to be transmitted to another device.
    [0033] For some embodiments, the LDPC code may be a high LDPC code. Additionally, for some embodiments, the base LDPC code may include one or more punctured nodes. The LDPC encoder 414 may then puncture one or more bits of the codeword that correspond to respective punctured nodes of the base LDPC code. These punctured codeword bits are not transmitted by transceiver 430. For some embodiments, the punctured nodes may include a base variable node having a degree equal to, or less than, a number of LDPC code check nodes. For example, at least one of the punctured nodes may be a higher degree variable node of the LDPC code. For other embodiments, at least one of the punctured nodes can be used to split a check node that is connected to a variable node of the LDPC code by two or more edges. Such a perforated node can be used to eliminate double edges in the base graph for elevated LDPC code.
    [0034] The decoder 420 includes a memory 422 and an LDPC decoder 424. The memory 422 stores the codewords, received through the transceiver 430, to be decoded by the LDPC decoder 424. The LDPC decoder 424 processes the codewords. code stored in memory 424 by iteratively performing parity check operations, using an LDPC code, and attempting to correct any bits that may have been received in error. For some embodiments, the LDPC code may be a high LDPC code. Further, for some embodiments, the received codeword may include one or more puncturing bits as determined, for example, based on a set of punctured nodes of the corresponding LDPC code. As described above with respect to FIG. 3, the punctured nodes can be determined based on the varying node degrees of the LDPC code. The LDPC decoder 424 can then treat these punctured nodes as erased for decoding purposes. For example, the LDPC 424 decoder can set the log-likelihood ratios (LLRs) of drilled nodes to zero at startup.
    [0035] For some embodiments, the LDPC decoder 424 may include a plurality of processing elements to perform the parity check or variable node operations in parallel. For example, when processing a codeword with elevation Z size, the LDPC decoder 424 can use a number (Z) of processing elements to perform parity checking operations on all Z edges of an elevated graph simultaneously. Specifically, each parity check operation may involve reading a corresponding soft bit value from memory 422, combining the soft bit value with other soft bit values associated with the check node, and writing a soft bit back to the memory 422 that results from the check node operation. A double edge in a base LDPC code can trigger parallel reading of the same memory location of the soft bit value twice during a single parity check update. Thus, additional circuitry is typically required to combine the soft bit values that are written back to memory in order to properly incorporate both updates. However, elimination of double edges in the LDPC code, for example, as described above with respect to FIG. 3, helps to avoid this extra complexity.
    [0036] FIG. 5 is an illustrative flowchart depicting an LDPC 500 encoding operation in accordance with some embodiments. Referring, for example, to FIG. 4, encoder 410 first receives a set of information bits to be encoded (510). Information bits may correspond to data intended to be transmitted to another device (eg, a receiving device) over a communications channel or network. For example, bits of information may be received from a central processing unit (CPU) and stored in memory 412.
    [0037] Encoder 410 may then perform an LDPC encoding operation on the information bits to produce an LDPC codeword (520). For some embodiments, the LDPC encoder 414 may encode the information bits in the LDPC codewords based on an LDPC code that is shared by the encoder 410 and a corresponding decoder (e.g., of the receiving device). Each codeword may include the original information bits, or a portion thereof, as well as a set of parity bits that may be used (e.g., by the decoder) to perform parity check operations on and/or retrieve the original bits of information. Encoder 410 may further puncture one or more bits of the LDPC codeword based on punctured base variable nodes of the LDPC code (530). For example, the one or more punctured codeword bits may correspond to one or more punctured base variable nodes, respectively, of the base LDPC code. Specifically, at least some of the perforated nodes are provided to eliminate multiple edges between node pairs in the base graph of the elevated LDPC code. For some embodiments, the punctured nodes may include a variable node having a degree equal to, or less than, a number of LDPC code verification nodes. For other embodiments, at least one of the punctured nodes may be a Grade 2 variable node. For example, the Grade 2 variable node may be used to split a check node that would otherwise be connected to another variable node of the code. LDPC by two or more edges. For some modalities both can occur, specifically, either a high-grade perforated variable node or a grade two perforated node may occur in the base plot. For some embodiments, the LDPC code may be a high LDPC code. Still additionally, the LDPC code can be based on a quasi-cyclic uplift, the edge group permutations being cyclical permutations.
    [0038] FIG. 6 is an illustrative flowchart depicting an LDPC 600 decoding operation in accordance with some embodiments. Referring, for example, to FIG. 4, decoder 420 first receives an LDPC codeword to be decoded (610). The LDPC codeword may be received from a transmission device, for example, in the form of a quadrature amplitude modulated (QAM) data signal. Consequently, the LDPC codeword may correspond to a subset of labeling bits of the demapped QAM data signal.
    [0039] Decoder 420 may identify one or more punctured bits of the LDPC codeword based on punctured base nodes of the LDPC code (620). For example, the one or more punctured codeword bits may correspond to one or more punctured base nodes, respectively, of the LDPC code. As described above, at least some of the perforated base nodes are provided to eliminate multiple edges between node pairs in the base graph of the elevated LDPC code. For some embodiments, the punctured nodes may include a variable node having a degree equal to, or less than, a number of LDPC code verification nodes. For other embodiments, at least one of the drilled nodes can be a Grade 2 variable node. As described above, the Grade 2 variable node can be used to split a check node that would otherwise be connected to another code variable node of LDPC by two or more edges. For some embodiments, the LDPC code may be a high LDPC code (eg, based on a quasi-cyclic survey).
    [0040] Decoder 420 may then perform an LDPC decoding operation on the received codeword to recover the original information bits (630). For example, the LDPC decoder 424 may process the codeword by iteratively performing parity check operations, using the LDPC code, and attempting to correct any bits that may have been received in the error. For some embodiments, the LDPC decoder 424 may treat the punctured codeword bits as cleared during the decoding operation, for example, by setting the LLRs of the punctured nodes to zero at startup.
    [0041] In the present embodiments, each of the LDPC codes can be viewed as a two-dimensional binary matrix of size Zxn, where n is the length of the base (transmission) block. For some embodiments, the proposed downstream codes are defined so that Z=360. IN each constellation, k bits can be taken at a time, per dimension (eg, for 1024QAM, k=5). Furthermore, k is a factor of 360, and k bits can be taken at a time column by column, thus generating 360/k dimensions or 180/k symbols per column. It should then be noted that k is a factor of 60 for the set k {1, 2, 3, 4, 5, 6}, in the cases of interest.
    [0042] FIGs. 7, 8, and 9 show exemplary parity check matrices 700, 800, and 900, respectively, in accordance with some embodiments. In each of the 700, 800, and 900 parity check matrices, the top row provides the indices for the columns of H. The second row indicates the information (1) and parity (0) columns. The third row indicates transmitted columns (1) and drilled columns (0).
    [0043] Note that parity check matrices 700 and 800, which are associated with LDPC codes with rates r = 27/30 and r = 13/15, respectively, are systematic. However, the parity check matrix 900, which is associated with an LDPC code with rate r = 21/28, has a perforated information column, and is therefore not completely systematic.
    [0044] Additionally, the parity check matrix 700 has a punctured degree two variable node (index 0). Such a node can split a single parity check into two. This ensures that the base matrix does not have double edges, and facilitates some of the modalities described here. An equivalent code representation can be constructed by merging the two parity checks and eliminating the punctured degree two variable node. Also, such an equivalent representation must have double or multiple borders on the base graph.
    [0045] FIG. 10 is a block diagram of a communications device 1000 according to some embodiments. Communications device 1000 includes a transceiver 1010, a processor 1020, and memory 1030. The transceiver 1010 may be used to communicate data to and/or from the communications device 1000. For example, the transceiver 1010 may receive and/or transmit bits of information between the communications device 1000 and the CPU. Encoder interface 1010 may also produce and/or receive LDPC codewords between communications device 1000 and another communications device on a network.
    [0046] Memory 1030 may include a data store 1032 which may be used as a local cache to store received information bits and/or codewords. In addition, memory 1030 may also include non-transient computer-readable storage media (e.g., one or more non-volatile memory elements such as EPROM, EEPROM, flash memory, a hard disk, etc.) that can store the following software modules: • an LDPC encoding module 1034 for encoding a set of information bits, using an LDPC code, to produce a codeword; • an LDPC decoding module 1036 for decoding LDPC codewords using an LDPC code. Each software module may include instructions which, when executed by processor 1020, may cause encoder 1000 to perform the corresponding function. Thus, the non-transient computer-readable storage media of memory 1030 may include instructions for performing all or a portion of the operations described above with respect to FIGS. 5-6. It should be noted that while modules 1034-1036 are illustrated as software in memory 1030, any of the modules may be implemented in hardware, software, firmware, or a combination of the above.
    [0047] Processor 1020, which is coupled between encoder interface 1010 and memory 1030, may be any suitable processor capable of executing scripts of instructions from one or more software programs stored in decoder 1000 (e.g., within memory 1030). For example, processor 1020 can run LDPC encoding module 1034 and/or LDPC decoding module 1036.
    [0048] The LDPC encoding module 1034 may be executed by the processor 1020 to encode the information bits, using the LDPC code, to produce a codeword. For example, processor 1020, in executing LDPC encoding module 1034, can perform an LDPC encoding operation on information bits based on an LDPC code that is shared by LDPC encoding module 1034 and an LDPC encoding module. decoding a corresponding receiving device. Each codeword may include the original information bits as well as a set of parity bits that can be used to perform parity checks on and/or retrieve the original information bits. For some embodiments, the LDPC code may be a high LDPC code (eg, based on a quasi-cyclic survey).
    [0049] Processor 1020, in executing the LDPC encoding module 1034, may further puncture one or more bits of the codeword based on the corresponding LDPC code. For example, the one or more punctured codeword bits may correspond to one or more punctured nodes, respectively, of the LDPC code. As described above, at least some of the punctured nodes are provided to eliminate multiple edges between node pairs in the base graph for the elevated LDPC code. For some embodiments, the punctured nodes may include a variable node having a degree equal to, or less than, a number of LDPC code verification nodes. For other embodiments, at least one of the punctured nodes may be a grade 2 variable node (eg, used to split a check node that would otherwise be connected to another LDPC code variable node by two or more edges).
    [0050] The LDPC decoding module 1036 can be executed by the processor 1020 to decode the LDPC codewords using the LDPC code. For some embodiments, processor 1020, in executing LDPC decoding module 1036, may first identify one or more punctured bits of a received codeword based on the LDPC code. Processor 1020 may then perform an LDPC decoding operation on the received codeword, while treating the punctured codeword bits as cleared. For example, the LDPC decoding module 1036, as performed by processor 1020, can set the LLRs of punctured nodes to zero at startup. For some embodiments, the LDPC code may be a high LDPC code (eg, based on a quasi-cyclic survey).
    [0051] As described above, punched codeword bits can correspond to the respective punched nodes of the LDPC code, with at least some of the punched nodes being provided to eliminate multiple edges between node pairs in the base graph for the punch code. High LDPC. For some embodiments, the punctured nodes may include a variable node having a degree equal to, or less than, a number of LDPC code verification nodes. For other embodiments, at least one of the punctured nodes may be a grade 2 variable node (eg, used to split a check node that would otherwise be connected to another LDPC code variable node by two or more edges).
    [0052] In the previous specification, the present embodiments were described with respect to the specific exemplary embodiments thereof. It will, however, be apparent that various modifications and changes may be made without departing from the broader scope of disclosure as set forth in the appended claims. The specification and drawings, therefore, should be considered in an illustrative rather than a restrictive sense. For example, the steps of the method illustrated in the flow charts of Figs. 5-6 may be performed in other suitable orders, multiple steps may be combined into a single step, and/or some steps may be omitted.
    权利要求:
    Claims (6)
    [0001]
    1. Data encoding method, the method characterized in that it comprises: receiving a set of information bits; performing an LDPC high-low-density parity check coding operation on the set of information bits to produce a codeword of a corresponding high LDPC high code using a cumulative lift G group, where the G group consists of Z elements g0, g1,..., gZ-1, the group multiplication rule being gigj=gk, where the raised codeword using the group G consists of n elements of the form y -ib
    [0002]
    2. Method according to claim 1, characterized in that the lifting group is a cyclic group, in which: gi can be identified with xi; the determinant of the quadratic submatrix is in the form:
    [0003]
    3. Method according to claim 1, characterized in that all elements below the first subdiagonal of the quadratic submatrix are equal to 0.
    [0004]
    4. Memory characterized in that it comprises instructions which, when executed by a processor provided within a communications device, cause the device to perform the method as defined in any one of claims 1 to 3.
    [0005]
    5. Encoder characterized in that it comprises: means for receiving a set of information bits; means for performing a low density high parity check, LDPC, coding operation on the set of information bits to produce a codeword of a corresponding high LDPC high code using a cumulative lift G group, where the G group consists of Z elements g0, g1,..., gZ-1, the group multiplication rule being gigj=gk, where the raised codeword using the group G consists of n elements of the form
    [0006]
    6. Communications device (4oo) characterized in that it comprises an encoder as defined in claim 5.
    类似技术:
    公开号 | 公开日 | 专利标题
    BR112015019409B1|2022-01-11|LDPC DESIGN USING NEAR-CYCLIC CONSTRUCTIONS AND DRILLING FOR HIGH RATE, HIGH PARALLELISM, AND LOW ERROR FLOOR
    US8661310B2|2014-02-25|Memory-efficient LDPC decoding
    KR100899738B1|2009-05-27|Ldpc decoder and decoding based on node memory
    US20090319860A1|2009-12-24|Overcoming ldpc trapping sets by decoder reset
    BRPI1100829B1|2021-02-23|method and apparatus for providing low density parity check | encoding and decoding
    BR112019009090A2|2019-11-12|method and apparatus for encoding and decoding ldpc codes
    WO2015123979A1|2015-08-27|Encoding method, decoding method, encoding device and decoding device for structured ldpc
    Sridharan et al.2004|Convergence analysis of a class of LDPC convolutional codes for the erasure channel
    US10090862B2|2018-10-02|Hybrid soft decoding algorithm for multiple-dimension TPC codes
    BR112019027688A2|2020-09-15|CODING METHOD, DECODING METHOD, APPLIANCE, COMMUNICATION APPLIANCE, TERMINAL, BASE STATION, COMMUNICATION SYSTEM, COMPUTER-READABLE STORAGE MEDIA, AND COMPUTER PROGRAM PRODUCT
    EP2890016A1|2015-07-01|Ldpc encoder and decoder
    US20160049962A1|2016-02-18|Method and apparatus of ldpc encoder in 10gbase-t system
    TWI407703B|2013-09-01|Multi-code ldpc | decoder
    EP3408956B1|2020-12-23|Apparatus and method for multi-code distributed storage
    WO2019042543A1|2019-03-07|Decoding of low-density parity-check convolutional turbo codes
    Ma et al.2015|Recursive encoding of spatially coupled LDPC codes with arbitrary rates
    WO2011010286A2|2011-01-27|Compact decoding of punctured codes
    BR112019020898B1|2022-02-15|CODING AND DECODING METHOD, DEVICE, TERMINAL, BASE STATION, COMMUNICATION SYSTEM AND COMPUTER READable STORAGE MEDIA
    Soltanpur et al.2017|Lowering Error Floors by Concatenation of Low-Density Parity-Check and Array Code
    Ivaniš et al.2017|Low Density Parity Check Codes
    Hosoya et al.2009|Adaptive Decoding Algorithms for Low-Density Parity-Check Codes over the Binary Erasure Channel
    BR112019020158A2|2020-04-22|encoding method, decoding method, information processing method, device, terminal, base station, communication system, computer-readable storage media and computer program product
    Kim2006|The Design of Rate-Compatible Structured Low-Density Parity-Check Codes
    同族专利:
    公开号 | 公开日
    US9306601B2|2016-04-05|
    CN105075128B|2018-07-17|
    CN104981978A|2015-10-14|
    KR20150118992A|2015-10-23|
    JP2016510185A|2016-04-04|
    EP2957038B1|2020-06-10|
    BR112015019409A2|2017-07-18|
    KR102142142B1|2020-08-06|
    KR20150118993A|2015-10-23|
    US20140229788A1|2014-08-14|
    CN104981978B|2017-12-08|
    KR101662747B1|2016-10-06|
    EP2957037A1|2015-12-23|
    WO2014127140A1|2014-08-21|
    JP5976960B2|2016-08-24|
    JP2016507200A|2016-03-07|
    JP6542132B2|2019-07-10|
    CN105075128A|2015-11-18|
    EP2957038A1|2015-12-23|
    WO2014127129A1|2014-08-21|
    US20140229789A1|2014-08-14|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US6633856B2|2001-06-15|2003-10-14|Flarion Technologies, Inc.|Methods and apparatus for decoding LDPC codes|
    US6961888B2|2002-08-20|2005-11-01|Flarion Technologies, Inc.|Methods and apparatus for encoding LDPC codes|
    US6957375B2|2003-02-26|2005-10-18|Flarion Technologies, Inc.|Method and apparatus for performing low-density parity-check code operations using a multi-level permutation|
    KR100809619B1|2003-08-26|2008-03-05|삼성전자주식회사|Apparatus and method for coding/decoding block low density parity check code in a mobile communication system|
    KR100922956B1|2003-10-14|2009-10-22|삼성전자주식회사|Method for encoding of low density parity check code|
    KR20050118056A|2004-05-12|2005-12-15|삼성전자주식회사|Method and apparatus for channel encoding and decoding in mobile communication systems using multi-rate block ldpc codes|
    US7346832B2|2004-07-21|2008-03-18|Qualcomm Incorporated|LDPC encoding methods and apparatus|
    US7143333B2|2004-08-09|2006-11-28|Motorola, Inc.|Method and apparatus for encoding and decoding data|
    US7506238B2|2004-08-13|2009-03-17|Texas Instruments Incorporated|Simplified LDPC encoding for digital communications|
    US7996746B2|2004-10-12|2011-08-09|Nortel Networks Limited|Structured low-density parity-check code|
    CN100550655C|2004-11-04|2009-10-14|中兴通讯股份有限公司|A kind of encoder/decoder of low density parity check code and generation method thereof|
    KR100856235B1|2005-09-26|2008-09-03|삼성전자주식회사|Apparatus and method for encoding and decoding block low density parity check codes with a variable coding rate|
    US8132072B2|2006-01-06|2012-03-06|Qualcomm Incorporated|System and method for providing H-ARQ rate compatible codes for high throughput applications|
    US8347173B2|2006-03-30|2013-01-01|Fujitsu Limited|Construction of parity-check matrices for non-binarys LDPC codes|
    US8028216B1|2006-06-02|2011-09-27|Marvell International Ltd.|Embedded parity coding for data storage|
    KR101191196B1|2006-06-07|2012-10-15|엘지전자 주식회사|Method of encoding and decoding using a parity check matrix|
    CA2664918C|2006-10-26|2014-06-03|Qualcomm Incorporated|Coding schemes for wireless communication transmissions|
    KR101433375B1|2006-12-04|2014-08-29|삼성전자주식회사|Apparatus and method of encoding/decoding block low density parity check codes in a communication system|
    US8161363B2|2006-12-04|2012-04-17|Samsung Electronics Co., Ltd|Apparatus and method to encode/decode block low density parity check codes in a communication system|
    KR101280477B1|2007-01-24|2013-07-01|퀄컴 인코포레이티드|Ldpc encoding and decoding of packets of variable sizes|
    US8261155B2|2007-03-09|2012-09-04|Qualcomm Incorporated|Methods and apparatus for encoding and decoding low density parity check codes|
    KR101119302B1|2007-04-20|2012-03-19|재단법인서울대학교산학협력재단|Apparatus and method for encoding low density parity check codes in a communication system|
    KR20080102902A|2007-05-22|2008-11-26|삼성전자주식회사|Method and apparatus for designing low density parity check code with multiple code rate, and information storage medium thereof|
    US7966548B2|2007-06-29|2011-06-21|Alcatel-Lucent Usa Inc.|Method and system for encoding data using rate-compatible irregular LDPC codes based on edge growth and parity splitting|
    JP5354985B2|2007-07-30|2013-11-27|パナソニック株式会社|Encoding device and decoding device|
    CN101227193B|2008-02-02|2010-06-02|中国科学院计算技术研究所|Method and device for encoding and decoding low density check code|
    PL2099135T3|2008-03-03|2018-07-31|Samsung Electronics Co., Ltd.|Apparatus and method for channel encoding and decoding in communication system using low-density parity-check codes|
    US8433972B2|2009-04-06|2013-04-30|Nec Laboratories America, Inc.|Systems and methods for constructing the base matrix of quasi-cyclic low-density parity-check codes|
    US8484545B2|2009-04-23|2013-07-09|Georgia Tech Research Corporation|Secure communication using error correction codes|
    US8832520B2|2011-11-29|2014-09-09|California Institute Of Technology|High order modulation protograph codes|EP3035539A1|2014-12-19|2016-06-22|Xieon Networks S.à r.l.|Encoder, decoder and encoding method with low error floor|
    US10523364B2|2015-11-06|2019-12-31|Samsung Electronics Co., Ltd.|Channel coding framework for 802.11AY and larger block-length LDPC codes for 11AY with 2-step lifting matrices and in-place property|
    US10784901B2|2015-11-12|2020-09-22|Qualcomm Incorporated|Puncturing for structured low density parity checkcodes|
    US11043966B2|2016-05-11|2021-06-22|Qualcomm Incorporated|Methods and apparatus for efficiently generating multiple lifted low-density parity-checkcodes|
    US10454499B2|2016-05-12|2019-10-22|Qualcomm Incorporated|Enhanced puncturing and low-density parity-checkcode structure|
    US10313057B2|2016-06-01|2019-06-04|Qualcomm Incorporated|Error detection in wireless communications using sectional redundancy check information|
    US9917675B2|2016-06-01|2018-03-13|Qualcomm Incorporated|Enhanced polar code constructions by strategic placement of CRC bits|
    US10291354B2|2016-06-14|2019-05-14|Qualcomm Incorporated|High performance, flexible, and compact low-density parity-checkcode|
    KR20180009558A|2016-07-19|2018-01-29|삼성전자주식회사|Decoder using low-density parity-check code and memory controller including the same|
    CN109478959B|2016-07-27|2021-08-06|高通股份有限公司|Design of hybrid automatic repeat requestfeedback bits for polar codes|
    US10804933B2|2016-09-30|2020-10-13|Lg Electronics Inc.|QC LDPC code rate matching method and device therefor|
    CN107959501B|2016-10-17|2021-06-29|上海数字电视国家工程研究中心有限公司|LDPC encoder|
    WO2018079987A1|2016-10-24|2018-05-03|엘지전자 주식회사|Method for dividing carrying block of ldpc code and apparatus therefor|
    WO2018084735A1|2016-11-03|2018-05-11|Huawei Technologies Co., Ltd.|Efficiently decodable qc-ldpc code|
    EP3567730A4|2017-01-06|2020-09-02|LG Electronics Inc. -1-|Method for selecting ldpc base code in multi-lpdc code, and device therefor|
    CN108631925A|2017-03-24|2018-10-09|中兴通讯股份有限公司|A kind of quasi-circulating low-density parity check code processing method and device|
    RU2667772C1|2017-05-05|2018-09-24|Хуавэй Текнолоджиз Ко., Лтд.|Method and device for information processing and communication device|
    CN108809325B|2017-05-05|2022-01-28|上海数字电视国家工程研究中心有限公司|LDPC decoder|
    WO2018201540A1|2017-05-05|2018-11-08|华为技术有限公司|Information processing method and communication apparatus|
    CN110535474A|2017-05-05|2019-12-03|华为技术有限公司|The method of information processing, communication device|
    CN108988871A|2017-05-31|2018-12-11|电信科学技术研究院|A kind of coding method and device, computer storage medium|
    CN108988869B|2017-05-31|2021-07-30|大唐移动通信设备有限公司|Method and device for determining check matrix and computer storage medium|
    US10312939B2|2017-06-10|2019-06-04|Qualcomm Incorporated|Communication techniques involving pairwise orthogonality of adjacent rows in LPDC code|
    EP3588786A4|2017-06-15|2020-07-15|Huawei Technologies Co., Ltd.|Information processing method and communication apparatus|
    CN109327225B9|2017-06-27|2021-12-10|华为技术有限公司|Information processing method and device and communication equipment|
    CN110677157A|2017-06-27|2020-01-10|华为技术有限公司|Information processing method and device and communication equipment|
    WO2019018120A1|2017-07-07|2019-01-24|Qualcomm Incorporated|Communication techniques applying low-density parity-check code base graph selection|
    KR101917829B1|2017-11-30|2018-11-12|고려대학교 산학협력단|Method and apparatus for deciding decoding order for shuffled decoding of ldpc codes|
    WO2019226064A1|2018-05-22|2019-11-28|Huawei Technologies Co., Ltd.|Type-i qc-ldpc codes with efficient encoding and good error floor characteristic|
    KR101991447B1|2018-09-10|2019-06-20|국방과학연구소|The Method of Protograph LDPC codes Construction Robust to Block Interference and Fading|
    CN109639392B|2018-11-09|2020-03-27|清华大学|Construction method and system of space coupling LDPC code for broadcast channel transmission|
    法律状态:
    2018-11-13| B06F| Objections, documents and/or translations needed after an examination request according [chapter 6.6 patent gazette]|
    2020-03-03| B06U| Preliminary requirement: requests with searches performed by other patent offices: procedure suspended [chapter 6.21 patent gazette]|
    2021-10-26| B09A| Decision: intention to grant [chapter 9.1 patent gazette]|
    2022-01-11| B16A| Patent or certificate of addition of invention granted [chapter 16.1 patent gazette]|Free format text: PRAZO DE VALIDADE: 20 (VINTE) ANOS CONTADOS A PARTIR DE 13/02/2014, OBSERVADAS AS CONDICOES LEGAIS. |
    优先权:
    申请号 | 申请日 | 专利标题
    US201361764476P| true| 2013-02-13|2013-02-13|
    US61/764,476|2013-02-13|
    US14/179,942|2014-02-13|
    US14/179,871|2014-02-13|
    PCT/US2014/016261|WO2014127129A1|2013-02-13|2014-02-13|Ldpc design using quasi-cyclic constructions and puncturing for high rate, high parallelism, and low error floor|
    US14/179,871|US20140229788A1|2013-02-13|2014-02-13|Ldpc design for high rate, high parallelism, and low error floor|
    US14/179,942|US9306601B2|2013-02-13|2014-02-13|LDPC design for high parallelism, low error floor, and simple encoding|
    [返回顶部]